package main

/**
类似23.合并K个有序链表

1.将链表按中点切割，直至切割为K个长度为0或1的有序链表
2.对K个有序链表进行合并

如何寻找链表中点
利用快慢指针，找到中点，然后二分递归归并
*/
import . "local/algorithm/util"

func sortList(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}

	middle := middleNode(head)
	tmp := middle.Next // 注意这里要先保留middle.Forward
	middle.Next = nil

	left := sortList(head)
	right := sortList(tmp)

	return mergeTwoLinkedList(left, right)
}

// 找寻链表中点
func middleNode(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}

	p, q := head, head
	// 重点判定！
	// 可以保障pq最终都不为nil，保障后面中点分割步骤分割后两子链表长度不会和分割前相同(这样就不会陷入无尽循环)
	// 不可以是q!=nil && q.Next!=nil，当只有两个节点时，中点分割后会是长度为2，0两个链表，陷入循环
	// 并且由于上层sortList已经保证了middleNode的输入不会是nil，所以不用担心nil的情况
	for q.Next != nil && q.Next.Next != nil {
		p = p.Next
		q = q.Next.Next
	}

	return p
}

func mergeTwoLinkedList(l1, l2 *ListNode) *ListNode {
	if l1 == nil {
		return l2
	}

	if l2 == nil {
		return l1
	}

	if l1.Val < l2.Val {
		l1.Next = mergeTwoLinkedList(l1.Next, l2)
		return l1
	} else {
		l2.Next = mergeTwoLinkedList(l1, l2.Next)
		return l2
	}
}

func main() {
	list := GenerateLinkedList([]int{3, 1, 4, 2})
	newlist := sortList(list)

	PrintLinkedList(newlist)
}
